import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Quicksort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        System.out.println("请输入待处理数组个数个数：");
        int n = in.nextInt();

        int[] A = new int[n];
        System.out.println("请依次输入数值：");
        for (int i = 0; i < n; i++) {
            A[i] = in.nextInt();
        }

        System.out.println("输入数组为：");
        for (int i = 0; i < n; i++) {
            System.out.println(A[i]);
        }

        int left=0,right=A.length-1;
        QuickSort(A,left,right);

        System.out.println("快速排序后的数组为：");
        for(int i=0;i<n;i++){
            System.out.println(A[i]);
        }
    }

    public static int HoarePartion(int [] A,int left,int right){
        int p=A[left];
        int i=left+1,j=right;
        while (i<j){
            while (A[i]<p){
                i=i+1;
            }
            while (A[j]>p){
                j=j-1;
            }
            int m=A[i];
            A[i]=A[j];
            A[j]=m;
        }
        int m=A[i];
        A[i]=A[j];
        A[j]=m;

        m=A[left];
        A[left]=A[j];
        A[j]=m;
        return j;
    }

    public static void QuickSort(int [] A,int left,int right){
        if(left<right){
            int s=HoarePartion(A,left,right);
            QuickSort(A,left,s-1);
            QuickSort(A,s+1,right);
        }
    }
    }
